package katas.recursion;

import java.util.Arrays;
import java.util.Random;

public class MergeSort {

	private void merge(int[] a, int i, int m, int n){
		int[] temp = new int[n];
	
		int j = i; //start index of left part
		int k = i+m; //start index of right part
		for (int l = 0; l < temp.length; l++) {
			if(j < i+m){
				if(k < i+n){
					if(a[j] <= a[k])
						temp[l] = a[j++]; //pick first from left
					else
						temp[l] = a[k++];
				}
				else
					temp[l] = a[j++]; //pick first from left
			}
			else
				temp[l] = a[k++]; //pick first from right
		}
		
		for (int l = 0; l < temp.length; l++)
			a[i+l] = temp[l];
	}
	
	private void mergeSort(int[] a, int i, int n){
		if(n == 1)
			return;
		else{
			int m = n/2;
			mergeSort(a, i, m);
			mergeSort(a, i+m, n-m);
			merge(a, i, m, n);
		}
	}
	
	public static void main(String[] args) {
		MergeSort ms = new MergeSort();
		
		int n = 1000000;
		int a[] = new int[n];
		Random r = new Random();
		for (int i = 0; i < n; i++) {
			a[i] = r.nextInt(Integer.MAX_VALUE);
		}
		
		//int a[] = {3, 37, 64, 58, 6, 61, 90, 71};
		
		int b[] = Arrays.copyOf(a, n);
		int c[] = Arrays.copyOf(a, n);
		
		long t1 = System.currentTimeMillis();
		ms.mergeSort(b, 0, a.length);
		System.out.println("My method took " + (System.currentTimeMillis()-t1) + "ms. ");
		
		t1 = System.currentTimeMillis();
		Arrays.sort(c);
		System.out.println("Java took " + (System.currentTimeMillis()-t1) + "ms. ");
		
		System.out.print(Arrays.equals(b, c));
		
//		for (int i = 0; i < a.length; i++)
//			System.out.print(a[i] + " ");
	}
}
